package simple.动态规划;

/**
 * <a href="https://leetcode-cn.com/problems/climbing-stairs">70. 爬楼梯</a>
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 * 注意：给定 n 是一个正整数。
 * 示例 1：
 *   输入： 2
 *   输出： 2
 *   解释：有两种方法可以爬到楼顶。
 *     1.  1 阶 + 1 阶
 *     2.  2 阶
 * 示例 2：
 *   输入： 3
 *   输出： 3
 *   解释： 有三种方法可以爬到楼顶。
 *     1.  1 阶 + 1 阶 + 1 阶
 *     2.  1 阶 + 2 阶
 *     3.  2 阶 + 1 阶
 * 解题思路：
 *   爬到 n 阶有两种方式，一种是从 n-2 到 n，另一种是 n-1 到 n，所以只需要知道爬到 n-2 和爬到 n-1 分别有多少种方法，
 *   再求和，就能得知爬到 n 阶有多少种方法，而爬到 n-2 和爬到 n-1 又可以按此方法类推。
 * @author 刘学松
 * @date 2021-07-16 15:19
 */
public class 爬楼梯 {
    public int climbStairs(int n) {
        if (n < 4) {
            return n;
        }
        int n1 = 2;
        int n2 = 3;
        for(int i=4; i<=n; i++) {
            int temp = n2;
            n2 += n1;
            n1 = temp;
        }
        return n2;
    }
}
